/*
 * @Autor: taobo
 * @Date: 2020-09-23 21:08:01
 */
#include "lock_free_queue.h"

#include <algorithm>
#include <cstring>

inline bool is_power_of_2(uint32_t num) {
  return (num != 0 && (num & (num-1)) == 0);
}

// 生成 32 bits 的 2 的幂指数
inline uint32_t hightest_one_bit(uint32_t num) {
  num |= (num >> 1);
  num |= (num >> 2);
  num |= (num >> 4);
  num |= (num >> 8);
  num |= (num >> 16);
  return num - (num >> 1); 
}

// 向上取 2 的幂指数
inline uint32_t roundup_pow_of_two(uint32_t num) {
  return num > 1 ? hightest_one_bit((num - 1) << 1) : 1; 
}

LockFreeQueue::LockFreeQueue(uint32_t size) : _in(0), _out(0) {
  _size = is_power_of_2(size) ? size : roundup_pow_of_two(size);
  _buffer = new uint8_t[_size];
}

LockFreeQueue::~LockFreeQueue() {
  if (_buffer)
    delete[] _buffer;
}

bool LockFreeQueue::put(const uint8_t *buffer, uint32_t len) {
  uint32_t oldval = len;
  len = std::min(len, _size - (_in - _out.load(std::memory_order_acq_rel)));
  if (oldval != len)
    return false;
  // smp_mb 内存屏障， 上读 out , 下写
  uint32_t l = std::min(len, _size - (_in & (_size - 1)));
  memcpy(_buffer + (_in & (_size - 1)), buffer, l);
  memcpy(_buffer, buffer + l, len - l);
  // smp_wrb 写内存屏障， 确保更新 in 时已将数据全部写入
  _in.fetch_add(len, std::memory_order_release);
  return true;
}

bool LockFreeQueue::get(uint8_t *buffer, uint32_t len) {
  uint32_t oldval = len;
  len = std::min(len, _in.load(std::memory_order_acq_rel) - _out);
  if (oldval != len)
    return false;
  // smp_rmb 读内存屏障
  uint32_t l = std::min(len, _size - (_out & (_size - 1)));
  memcpy(buffer, _buffer + (_out & (_size - 1)), l);
  memcpy(buffer + l, _buffer, len - l);
  // smp_mb 内存屏障上读下写
  _out.fetch_add(len, std::memory_order_acq_rel);
  return true;
}